package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         296,
		Discription: "最小曼哈顿距离之和的碰面地点",
		Level:       3,
		Labels: map[string]int{
			"矩阵":  1,
			"数学":  1,
			"奇偶性": 1,
		},
	})
}

//找初始所有人位置的x中位数、y中位数，中位数就是碰面地点
func MinTotalDistance(grid [][]int) int {
	rows, cols := []int{}, []int{}

	// Collect all the x-coordinates
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == 1 {
				rows = append(rows, i)
			}
		}
	}

	// Collect all the y-coordinates
	for j := 0; j < len(grid[0]); j++ {
		for i := 0; i < len(grid); i++ {
			if grid[i][j] == 1 {
				cols = append(cols, j)
			}
		}
	}

	// Function to find the median
	findMedian := func(arr []int) int {
		n := len(arr)
		mid := n / 2
		if n%2 == 0 {
			return (arr[mid-1] + arr[mid]) / 2
		}
		return arr[mid]
	}

	medianRow := findMedian(rows)
	medianCol := findMedian(cols)

	// Calculate total distance to the median
	totalDistance := 0
	for _, r := range rows {
		delta := r - medianRow
		if delta >= 0 {
			totalDistance += delta
		} else {
			totalDistance -= delta
		}
	}
	for _, c := range cols {
		delta := c - medianCol
		if delta >= 0 {
			totalDistance += delta
		} else {
			totalDistance -= delta
		}
	}

	return totalDistance
}
